The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

U11(tt, V2) → U12(isNat(activate(V2)))
U12(tt) → tt
U21(tt) → tt
U31(tt, N) → activate(N)
U41(tt, M, N) → U42(isNat(activate(N)), activate(M), activate(N))
U42(tt, M, N) → s(plus(activate(N), activate(M)))
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → U11(isNat(activate(V1)), activate(V2))
isNat(n__s(V1)) → U21(isNat(activate(V1)))
plus(N, 0) → U31(isNat(N), N)
plus(N, s(M)) → U41(isNat(M), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(X1, X2)
activate(n__s(X)) → s(X)
activate(X) → X

Rewrite Strategy: INNERMOST

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(n¹):
The rewrite sequence
U11(tt, n__plus(n__0, V284_3)) →⁺ U12(U11(tt, V284_3))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
The pumping substitution is [V284_3 / n__plus(n__0, V284_3)].
The result substitution is [ ].

(2) BOUNDS(n^1, INF)